#include<iostream>
#include<vector>
using namespace std;
/*
1.下标0位置作为哨兵位
2.ne数组为指针域，ne[i] = 0 代表空指针，后续没有结点
3.e[i]和ne[i]是绑在一起使用的，也可以写成一种结构体的形式，例如：
    struct node
    {
        int e, ne;
    }list[N];
4.哈希表：mp[i]表示i在这个元素中存放的位置
*/
const int N = 1e5 + 10;
int h; // 头指针
int id; //下一个元素分配的位置
int e[N], ne[N]; //数据域、指针域
int mp[N];
// 遍历链表
void print()
{
    for(int i = ne[h]; i; i = ne[i])
        cout << e[i] << " ";
    cout << endl;
}
// 头插
void push_front(int x)
{
    // 在数据域先放x
    e[++ id] = x;
    mp[x] = id;//标记x的存储位置

    // 修改指针 1. x的右指针指向哨兵位的后继  2. 哨兵位的右指针指向x
    ne[id] = ne[h];
    ne[h] = id;  
}
// 按值查找
int find(int x)
{
    //方法一：遍历链表
    for(int i = ne[h]; i; i = ne[i])
        if(e[i] == x) return i;
    
    return 0;
    
    //方法二：使用哈希表优化
    //return mp[x];
}
//在任意元素之后插入x
void insert(int p, int x)
{
    //先放x
    e[++ id] = x;
    mp[x] = id;
    //注意顺序
    ne[id] = ne[p];
    ne[p] = id;
}
//删除任意位置之后的元素
void erase(int p)
{
    //不能是最后一个元素
    if(ne[p])
    {
        mp[e[ne[p]]] = 0;
        ne[p] = ne[ne[p]];
    }
}
int main()
{
    for(int i = 1; i <= 5; i ++)
    {
        push_front(i);
        print();
    }
    return 0;
}